Today many commercial distributed database systems may deploy an unordered hierarchical key space for composite database record keys. Database records may be distributed among a hierarchy of database servers and processing a user query for retrieving database records with multiple record keys may involve a different database server for each of the multiple record keys in order to retrieve the requested database records. The data schema information may be present on all servers or it may be distributed consistent with the distribution of database records. For each of the multiple record keys, a lookup may be made based on the data type of the key to find a server in a hierarchy of servers storing a range of records that include the next record key. A lookup based on the data type of the next key may occur on the next server and so on until the location of the data record is found. The multiple record keys of the composite database record key may be in a distributed index. The comparisons of the multiple lookup for each key of the composite record key are performed sequentially and may also be distributed, resulting in inefficient lookup of composite record keys to retrieve a record.
In other distributed databases, hashing of composite record keys may be used where ranges of records are randomly distributed among database servers. Unfortunately, these composite keys are also unordered and distributed among the servers so that it is inefficient to sort composite record keys.
What is needed is a way to provide composite record keys that may be efficiently sorted and compared for a large distributed database. Such a system and method should support maintenance of the metadata on one or few machines and not be distributed with the data records. Furthermore, a high throughput should be achieved for composite key sorting with minimal state transfer between servers.